The rise of cloud computing leads to new opportunities for biometric applications. Large biometric databases can be stored at small cost on servers that are accessible by any device, even with low computational capacities. However, using remote databases on untrusted servers raises privacy issues, especially with biometric data that are particularly sensitive.
Two main concerns are the confidentiality of these data and the privacy of access patterns. Encryption alone is consequently insufficient, since it does not protect the access patterns. Furthermore, encrypting data can have a big impact on the usability of the database. If the user has to retrieve the whole database to perform an identification protocol, then he loses the benefit of outsourcing his data. It has been proposed in EP2248071 an identification protocol over encrypted biometric data that preserves the privacy of the users. The identification process follows the structure of the “Beacon Guided Search” (BGS) introduced by Hao et al. in the publication by F. Hao, J. Daugman, and P. Zielinsky, “A fast search algorithm for a large fuzzy database”, IEEE Transactions on Information Forensics and Security, 3(2):203-212, 2008.
In this scheme, to identify a biometric acquisition against a database, this acquisition is hashed by several locality-sensitive hash functions. These hash functions output, with good probability, the same value on data that are sufficiently close and different values for data that are sufficiently different.
More specifically, the mathematical definition of a Locality-Sensitive Hashing function (LSH function) is as follows: let B be a metric space, U a set with smaller dimensionality, r1,r2∈ with r1<r2, and p1,p2∈[0,1] with pt>p2. A family H={H1, . . . , Hk}, Hj:B→U is (r1,r2,p1,p2)−LSH if for all h∈H, x, x′∈B, Pr[h(x)=h(x′)]>p1 if dB(x,x′)<r1) and Pr[h(x)=h(x′)]<p2 if dB(x,x′)>r2.
The elements of the database that lead to common hashed values are then selected for full matching operations from which we can deduct the identification results.
The biometric references are stored in an encrypted fashion in one remote biometric database. In other remote database, the hashed values of these references are also encrypted and stored.
To achieve this scheme while preserving privacy of the access patterns, some cryptographic patterns known as private information retrieval (PIR) and private information storage (PIS) are used; that respectively enable to read from or to write on a database, without revealing the indices of the data that are read (resp. written).
Unfortunately, such protocols are not yet usable in practice, especially with the sizes of the databases and the number of requests considered in the aforementioned publication, as they are too costly in terms of computation time.
Moreover, the identification protocol disclosed in EP2248071 requires the use of Bloom filters, which make it even more costly in computation time and even less efficient.
For these reasons there is a need for providing a more efficient identification method, for using data stored in a remote storage system, which ensures both data confidentiality and privacy of the access patterns.